package com.leetcode.array;

/**
 * 15. 三数之和
 * 提示
 * 中等
 * 6.2K
 * 相关企业
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * 你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 * 示例 2：
 *
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 * 示例 3：
 *
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 * 提示：
 * 3 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Code15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>  res = new ArrayList<>();
        Arrays.sort(nums);
        for(int f=0;f<nums.length;f++){
            if(f > 0 && nums[f]  == nums[f-1]){
                continue;
            }
            if(nums[f] > 0){
                break;
            }
            int target = nums[f] * -1;
            int t = nums.length-1;
            for(int s=f+1;s<nums.length;s++){
                if(s > f + 1 && nums[s] == nums[s-1]){
                    continue;
                }

                while (s < t && nums[s] + nums[t] > target){
                    t--;
                }
                if(s >= t){
                    break;
                }
                if(nums[s] + nums[t] == target){
                    List<Integer> list = new ArrayList<>(3);
                    list.add(nums[f]);
                    list.add(nums[s]);
                    list.add(nums[t]);
                    res.add(list);
                }
            }
        }
        return res;
    }
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>>  res = new ArrayList<>();
        Arrays.sort(nums);
        int leftIndex = 0;
        int rightIndex = nums.length-1;
        while (leftIndex < nums.length-1 && nums[leftIndex] <= 0){
            int lp = leftIndex;
            int rp = rightIndex;
            while (rp >= 0 && nums[rp] >= 0 ){
                int min = nums[lp];
                int max = nums[rp];
                int target = (max + min) * -1;
                if(target > nums[rp]){
                    break;
                }
                boolean flag = getTargetIndex(nums, target, lp+1, rp-1);
                if(flag){
                    List<Integer> list = new ArrayList<>();
                    list.add(min);
                    list.add(max);
                    list.add(target);
                    res.add(list);
                    while (rp -1 >= 0 && nums[rp] == nums[rp-1]){
                        rp--;
                    }
                }
                rp--;
            }
            while (leftIndex+1 < nums.length-1 && nums[leftIndex] == nums[leftIndex+1]){
                leftIndex ++;
            }
            leftIndex ++;
        }
        return res;
    }

    private boolean getTargetIndex(int[] nums,int target,int leftIndex,int rightIndex){
        if(leftIndex < 0 || rightIndex > nums.length-1 || target < nums[leftIndex] || target > nums[rightIndex]){
            return false;
        }
        while (leftIndex <= rightIndex){
            int midIdnex = (leftIndex + rightIndex)/2;
            if(nums[midIdnex] == target){
                return true;
            }else if(nums[midIdnex] < target){
                leftIndex = midIdnex + 1;
            }else if(nums[midIdnex] > target){
                rightIndex = midIdnex - 1;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Code15 solution = new Code15();
        //int[] nums = new int[]{34,55,79,28,46,33,2,48,31,-3,84,71,52,-3,93,15,21,-43,57,-6,86,56,94,74,83,-14,28,-66,46,-49,62,-11,43,65,77,12,47,61,26,1,13,29,55,-82,76,26,15,-29,36,-29,10,-70,69,17,49};
        int[] nums = new int[]{1,2,-2,-1};
        // Arrays.sort(nums);
        List<List<Integer>> lists = solution.threeSum(nums);
        lists.forEach(list->{
            System.out.println(list);
            //System.out.println(list.get(0) + " + " + list.get(1) + " + " + list.get(2) + " = " + (list.get(0)+list.get(1)+list.get(2)));
        });

    }
}
